class SmallestInfiniteSet
{
public:
    SmallestInfiniteSet()
    {
    }

    int popSmallest()
    {
        int i = 1;
        while (notIn.count(i))
        {
            ++i;
        }
        notIn.insert(i);
        return i;
    }

    void addBack(int num)
    {
        if (notIn.count(num))
        {
            notIn.erase(num);
        }
    }

private:
    set<int> notIn;
};
class SmallestInfiniteSet
{
public:
    SmallestInfiniteSet()
    {
        this->threshold = 1;
    }

    int popSmallest()
    {
        int result = -1;
        if (this->nums.empty())
        {
            result = this->threshold;
            ++this->threshold;
            return result;
        }
        result = *this->nums.begin();
        this->nums.erase(this->nums.begin());
        return result;
    }

    void addBack(int num)
    {
        if (num >= this->threshold)
        {
            return;
        }
        this->nums.insert(num);
    }

private:
    int threshold;
    set<int> nums;
};
/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */